SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Galactic algorithm</title>

</head>

Galactic algorithm

</h1>

</header>

A galactic algorithm is an <a href="Algorithm" title="Algorithm">algorithm</a> with record-breaking theoretical (<a href="Asymptotic_computational_complexity" title="Asymptotic computational complexity">asymptotic</a>) performance, but which is not used due to practical constraints. Typical reasons are that the performance gains only appear for problems that are so large they never occur, or the algorithm's complexity outweighs a relatively small gain in performance. Galactic algorithms were so named by <a href="Richard_Lipton" title="Richard Lipton">Richard Lipton</a> and Ken Regan,<a href="#cite_note-seminal-1">[1]</a> because they will never be used on any data sets on Earth.

<div class="mw-heading mw-heading2"><h2 id="Possible_use_cases">Possible use cases</h2></div>

Even if they are never used in practice, galactic algorithms may still contribute to <a href="Computer_science" title="Computer science">computer science</a>:

<ul><li>An algorithm, even if impractical, may show new techniques that may eventually be used to create practical algorithms. See, for example, communication channel capacity, below.</li>

<li>Available computational power may catch up to the crossover point, so that a previously impractical algorithm becomes practical. See, for example, low-density parity-check codes, below.</li>

<li>An impractical algorithm can still demonstrate that <a href="Conjecture" title="Conjecture">conjectured</a> bounds can be achieved, or that proposed bounds are wrong, and hence advance the theory of algorithms (see, for example, Reingold's algorithm for <a href="Connectivity_(graph_theory)" title="Connectivity (graph theory)">connectivity</a> in undirected graphs). As Lipton states:<a href="#cite_note-seminal-1">[1]</a><style data-mw-deduplicate="TemplateStyles:r1244412712">

/* start https://en.wikipedia.org/ */

.mw-parser-output .templatequote{overflow:hidden;margin:1em 0;padding:0 32px}.mw-parser-output .templatequotecite{line-height:1.5em;text-align:left;margin-top:0}@media(min-width:500px){.mw-parser-output .templatequotecite{padding-left:1.6em}}

/* end https://en.wikipedia.org/ */

</style><blockquote class="templatequote">This alone could be important and often is a great reason for finding such algorithms. For example, if tomorrow there were a discovery that showed there is a factoring algorithm with a huge but provably polynomial time bound, that would change our beliefs about factoring. The algorithm might never be used, but would certainly shape the future research into factoring.</blockquote> Similarly, a hypothetical algorithm for the <a href="Boolean_satisfiability_problem" title="Boolean satisfiability problem">Boolean satisfiability problem</a> with a large but polynomial time bound, such as <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Theta {\bigl (}n^{2^{100}}{\bigr )}}">

</mrow>

<msup>

<msup>

</mrow>

</msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta {\bigl (}n^{2^{100}}{\bigr )}}</annotation>

</semantics>

</math><img src="./3aec58b531961b1f61c1374cca4808fc67df7a4e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:8.553ex; height:3.676ex;" alt="{\displaystyle \Theta {\bigl (}n^{2^{100}}{\bigr )}}" loading="lazy">, although unusable in practice, would settle the <a href="P_versus_NP_problem" title="P versus NP problem">P versus NP problem</a>, considered the most important open problem in computer science and one of the <a href="Millennium_Prize_Problems" title="Millennium Prize Problems">Millennium Prize Problems</a>.<a href="#cite_note-2">[2]</a><a href="#cite_note-3">[3]</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Examples">Examples</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Integer_multiplication">Integer multiplication</h3></div>

An example of a galactic algorithm is the fastest known way to <a href="Multiplication_algorithm" title="Multiplication algorithm">multiply two numbers</a>,<a href="#cite_note-4">[4]</a> which is based on a 1729-dimensional <a href="Fourier_transform" title="Fourier transform">Fourier transform</a>.<a href="#cite_note-quick-5">[5]</a> It needs <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n\log n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n\log n)}</annotation>

</semantics>

</math><img src="./9d2320768fb54880ca4356e61f60eb02a3f9d9f1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.118ex; height:2.843ex;" alt="{\displaystyle O(n\log n)}" loading="lazy"> bit operations, but as the constants hidden by the <a href="Big_O_notation" title="Big O notation">big O notation</a> are large, it is never used in practice. However, it also shows why galactic algorithms may still be useful. The authors state: "we are hopeful that with further refinements, the algorithm might become practical for numbers with merely billions or trillions of digits."<a href="#cite_note-quick-5">[5]</a>

<div class="mw-heading mw-heading3"><h3 id="Primality_testing">Primality testing</h3></div>

The <a href="AKS_primality_test" title="AKS primality test">AKS primality test</a> is galactic. It is the most theoretically sound of any known algorithm that can take an arbitrary number and tell if it is <a href="Prime_number" title="Prime number">prime</a>. In particular, it is provably polynomial-time, deterministic, and unconditionally correct. All other known algorithms fall short on at least one of these criteria, but the shortcomings are minor and the calculations are much faster, so they are used instead. <a href="Elliptic_curve_primality_proving" class="mw-redirect" title="Elliptic curve primality proving">ECPP</a> in practice runs much faster than AKS, but it has never been proven to be polynomial time. The <a href="Miller%E2%80%93Rabin_primality_test" title="Miller–Rabin primality test">Miller–Rabin</a> test is also much faster than AKS, but produces only a probabilistic result. However the probability of error can be driven down to arbitrarily small values (say <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle <10^{-100}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle <10^{-100}}</annotation>

</semantics>

</math><img src="./6b610ca49f45cf06d419f308eb5f17b2d4ace1f4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:8.755ex; height:2.676ex;" alt="{\displaystyle <10^{-100}}" loading="lazy">), good enough for practical purposes. There is also a <a href="Miller%E2%80%93Rabin_primality_test#Deterministic_variants" title="Miller–Rabin primality test">deterministic version</a> of the Miller-Rabin test, which runs in polynomial time over all inputs, but its correctness depends on the <a href="Generalized_Riemann_hypothesis" title="Generalized Riemann hypothesis">generalized Riemann hypothesis</a> (which is widely believed, but not proven). The existence of these (much) faster alternatives means AKS is not used in practice.

<div class="mw-heading mw-heading3"><h3 id="Matrix_multiplication">Matrix multiplication</h3></div>

The first improvement over brute-force <a href="Matrix_multiplication" title="Matrix multiplication">matrix multiplication</a> (which needs <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n^{3})}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n^{3})}</annotation>

</semantics>

</math><img src="./6b04f5c5cfea38f43406d9442387ad28555e2609.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.032ex; height:3.176ex;" alt="{\displaystyle O(n^{3})}" loading="lazy"> multiplications) was the <a href="Strassen_algorithm" title="Strassen algorithm">Strassen algorithm</a>: a recursive algorithm that needs <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n^{2.807})}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n^{2.807})}</annotation>

</semantics>

</math><img src="./5efdd8558feb6363dbd3fe296b5f757df910e88a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.955ex; height:3.176ex;" alt="{\displaystyle O(n^{2.807})}" loading="lazy"> multiplications. This algorithm is not galactic and is used in practice. Further extensions of this, using sophisticated <a href="Group_theory" title="Group theory">group theory</a>, are the <a href="Coppersmith%E2%80%93Winograd_algorithm" class="mw-redirect" title="Coppersmith–Winograd algorithm">Coppersmith–Winograd algorithm</a> and its slightly better successors, needing <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n^{2.373})}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n^{2.373})}</annotation>

</semantics>

</math><img src="./8b7e9678394c2c1edfe2bbe326ea0c90343eb68b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.955ex; height:3.176ex;" alt="{\displaystyle O(n^{2.373})}" loading="lazy"> multiplications. These are galactic – "We nevertheless stress that such improvements are only of theoretical interest, since the huge constants involved in the complexity of fast matrix multiplication usually make these algorithms impractical."<a href="#cite_note-6">[6]</a>

<div class="mw-heading mw-heading3"><h3 id="Communication_channel_capacity">Communication channel capacity</h3></div>

<a href="Claude_Shannon" title="Claude Shannon">Claude Shannon</a> showed a simple but asymptotically optimal <a href="Code" title="Code">code</a> that can reach the theoretical capacity of a <a href="Communication_channel" title="Communication channel">communication channel</a>. It requires assigning a random code word to every possible <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

<div class="mw-heading mw-heading3"><h3 id="Sub-graphs">Sub-graphs</h3></div>

The problem of <a href="Decision_problem" title="Decision problem">deciding</a> whether a graph <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"> contains <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H}</annotation>

</semantics>

</math><img src="./75a9edddcca2f782014371f75dca39d7e13a9c1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle H}" loading="lazy"> as a <a href="Graph_minor" title="Graph minor">minor</a> is <a href="NP-complete" class="mw-redirect" title="NP-complete">NP-complete</a> in general, but where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H}</annotation>

</semantics>

</math><img src="./75a9edddcca2f782014371f75dca39d7e13a9c1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle H}" loading="lazy"> is fixed, it can be solved in polynomial time. The running time for testing whether <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H}</annotation>

</semantics>

</math><img src="./75a9edddcca2f782014371f75dca39d7e13a9c1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle H}" loading="lazy"> is a minor of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"> in this case is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n^{2})}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n^{2})}</annotation>

</semantics>

</math><img src="./6cd9594a16cb898b8f2a2dff9227a385ec183392.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.032ex; height:3.176ex;" alt="{\displaystyle O(n^{2})}" loading="lazy">,<a href="#cite_note-kkr12-9">[9]</a> where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"> and the <a href="Big_O_notation" title="Big O notation">big O notation</a> hides a constant that depends superexponentially on <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H}</annotation>

</semantics>

</math><img src="./75a9edddcca2f782014371f75dca39d7e13a9c1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle H}" loading="lazy">. The constant is greater than <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2\uparrow \uparrow (2\uparrow \uparrow (2\uparrow \uparrow (h/2)))}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2\uparrow \uparrow (2\uparrow \uparrow (2\uparrow \uparrow (h/2)))}</annotation>

</semantics>

</math><img src="./360009b1d76b85fe5141886793eb89e9ad50e825.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:23.425ex; height:2.843ex;" alt="{\displaystyle 2\uparrow \uparrow (2\uparrow \uparrow (2\uparrow \uparrow (h/2)))}" loading="lazy"> in <a href="Knuth's_up-arrow_notation" title="Knuth's up-arrow notation">Knuth's up-arrow notation</a>, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h}</annotation>

</semantics>

</math><img src="./b26be3e694314bc90c3215047e4a2010c6ee184a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.339ex; height:2.176ex;" alt="{\displaystyle h}" loading="lazy"> is the number of vertices in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H}</annotation>

</semantics>

</math><img src="./75a9edddcca2f782014371f75dca39d7e13a9c1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle H}" loading="lazy">.<a href="#cite_note-10">[10]</a> Even the case of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h=4}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h=4}</annotation>

</semantics>

</math><img src="./9b3ec3aec2fcc1177dad3a297dfc9060ec07e5a3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.6ex; height:2.176ex;" alt="{\displaystyle h=4}" loading="lazy"> cannot be reasonably computed as the constant is greater than 2 <a href="Pentated" class="mw-redirect" title="Pentated">pentated</a> by 4, or 2 <a href="Tetrated" class="mw-redirect" title="Tetrated">tetrated</a> by 65536, that is, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2\uparrow \uparrow \uparrow 4={}^{65536}2=\underbrace {2^{2^{\cdot ^{\cdot ^{2}}}}} _{65536}}">

<msup>

</mrow>

</mrow>

</msup>

<msup>

<msup>

<msup>

<msup>

</mrow>

</msup>

</mrow>

</msup>

</mrow>

</msup>

</mrow>

</msup>

</munder>

</mrow>

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2\uparrow \uparrow \uparrow 4={}^{65536}2=\underbrace {2^{2^{\cdot ^{\cdot ^{2}}}}} _{65536}}</annotation>

</semantics>

</math><img src="./5787e6e37e6e31854ce4abe8dff3707f2fa8340c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.671ex; margin-right: -0.002ex; width:22.916ex; height:7.343ex;" alt="{\displaystyle 2\uparrow \uparrow \uparrow 4={}^{65536}2=\underbrace {2^{2^{\cdot ^{\cdot ^{2}}}}} _{65536}}" loading="lazy">.

<div class="mw-heading mw-heading3"><h3 id="Cryptographic_breaks">Cryptographic breaks</h3></div>

In <a href="Cryptography" title="Cryptography">cryptography</a> jargon, a "break" is any attack faster in expectation than <a href="Brute-force_attack" title="Brute-force attack">brute force</a> – i.e., performing one trial decryption for each possible key. For many cryptographic systems, breaks are known, but are still practically infeasible with current technology. One example is the best attack known against 128-bit <a href="Advanced_Encryption_Standard" title="Advanced Encryption Standard">AES</a>, which takes only <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{126}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{126}}</annotation>

</semantics>

</math><img src="./03ba78eeaf0f84e190d7aa90548b82ead88a37c5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.861ex; height:2.676ex;" alt="{\displaystyle 2^{126}}" loading="lazy"> operations.<a href="#cite_note-:0-11">[11]</a> Despite being impractical, theoretical breaks can provide insight into vulnerability patterns, and sometimes lead to discovery of exploitable breaks.

<div class="mw-heading mw-heading3"><h3 id="Traveling_salesman_problem">Traveling salesman problem</h3></div>

For several decades, the best known approximation to the <a href="Traveling_salesman_problem" class="mw-redirect" title="Traveling salesman problem">traveling salesman problem</a> in a <a href="Metric_space" title="Metric space">metric space</a> was the very simple <a href="Christofides_algorithm" title="Christofides algorithm">Christofides algorithm</a> which produced a path at most 50% longer than the optimum. (Many other algorithms could usually do much better, but could not provably do so.) In 2020, a newer and much more complex algorithm was discovered that can beat this by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 10^{-34}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 10^{-34}}</annotation>

</semantics>

</math><img src="./9cf2b5bceb62956a12c9ce5a253e838aa25c9f11.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.48ex; height:2.676ex;" alt="{\displaystyle 10^{-34}}" loading="lazy"> percent.<a href="#cite_note-12">[12]</a> Although no one will ever switch to this algorithm for its very slight worst-case improvement, it is still considered important because "this minuscule improvement breaks through both a theoretical logjam and a psychological one".<a href="#cite_note-13">[13]</a>

<div class="mw-heading mw-heading3"><h3 id="Hutter_search">Hutter search</h3></div>

A single algorithm, "Hutter search", can solve any well-defined problem in an asymptotically optimal time, barring some caveats. It works by searching through all possible algorithms (by runtime), while simultaneously searching through all possible <a href="Formal_proof" title="Formal proof">proofs</a> (by length of proof), looking for a proof of correctness for each algorithm. Since the proof of correctness is of finite size, it "only" adds a constant and does not affect the asymptotic runtime. However, this constant is so big that the algorithm is entirely impractical.<a href="#cite_note-14">[14]</a><a href="#cite_note-15">[15]</a> For example, if the shortest proof of correctness of a given algorithm is 1000 bits long, the search will examine at least 2999 other potential proofs first.

Hutter search is related to <a href="Solomonoff's_theory_of_inductive_inference" title="Solomonoff's theory of inductive inference">Solomonoff induction</a>, which is a formalization of <a href="Bayesian_inference" title="Bayesian inference">Bayesian inference</a>. All <a href="Computable" class="mw-redirect" title="Computable">computable</a> theories (as implemented by programs) which perfectly describe previous observations are used to calculate the probability of the next observation, with more weight put on the shorter computable theories. Again, the search over all possible explanations makes this procedure galactic.

<div class="mw-heading mw-heading3"><h3 id="Optimization">Optimization</h3></div>

<a href="Simulated_annealing" title="Simulated annealing">Simulated annealing</a>, when used with a logarithmic cooling schedule, has been proven to find the <a href="Global_optimum" class="mw-redirect" title="Global optimum">global optimum</a> of any optimization problem. However, such a cooling schedule results in entirely impractical runtimes, and is never used.<a href="#cite_note-16">[16]</a> However, knowing this ideal algorithm exists has led to practical variants that are able to find very good (though not provably optimal) solutions to complex optimization problems.<a href="#cite_note-17">[17]</a>

<div class="mw-heading mw-heading3"><h3 id="Minimum_spanning_trees">Minimum spanning trees</h3></div>

The <a href="Expected_linear_time_MST_algorithm" title="Expected linear time MST algorithm">expected linear time MST algorithm</a> is able to discover the <a href="Minimum_spanning_tree" title="Minimum spanning tree">minimum spanning tree</a> of a graph in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(m+n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(m+n)}</annotation>

</semantics>

</math><img src="./0922aa919079469e54e4c3affe9b7ab456f1a124.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.858ex; height:2.843ex;" alt="{\displaystyle O(m+n)}" loading="lazy">, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"> is the number of edges and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> is the number of nodes of the graph.<a href="#cite_note-18">[18]</a> However, the constant factor that is hidden by the <a href="Big_O_notation" title="Big O notation">Big O notation</a> is huge enough to make the algorithm impractical. An implementation is publicly available<a href="#cite_note-19">[19]</a> and given the experimentally estimated implementation constants, it would only be faster than <a href="Bor%C5%AFvka's_algorithm" title="Borůvka's algorithm">Borůvka's algorithm</a> for graphs in which <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m+n>9\cdot 10^{151}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m+n>9\cdot 10^{151}}</annotation>

</semantics>

</math><img src="./bc74100999273f6c2d96369163dbb6e20152e8dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:17.239ex; height:2.843ex;" alt="{\displaystyle m+n>9\cdot 10^{151}}" loading="lazy">.<a href="#cite_note-20">[20]</a>

<div class="mw-heading mw-heading3"><h3 id="Hash_tables">Hash tables</h3></div>

Researchers have found an algorithm that achieves the provably best-possible<a href="#cite_note-SuccinctDictionaries-21">[21]</a> asymptotic performance in terms of time-space tradeoff.<a href="#cite_note-22">[22]</a> But it remains purely theoretical: "Despite the new hash table’s unprecedented efficiency, no one is likely to try building it anytime soon. It’s just too complicated to construct."<a href="#cite_note-OptimalBalance-23">[23]</a> and "in practice, constants really matter. In the real world, a factor of 10 is a game ender.”<a href="#cite_note-OptimalBalance-23">[23]</a>

<div class="mw-heading mw-heading3"><h3 id="Connectivity_in_undirected_graphs">Connectivity in undirected graphs</h3></div>

Connectivity in undirected graphs (also known as USTCON, for Unconnected Source-Target CONnectivity) is the problem of deciding if a path exists between two nodes in an undirected graph, or in other words, if they are in the same <a href="Component_(graph_theory)" title="Component (graph theory)">connected component</a>. When the usage of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O({\text{N}})}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O({\text{N}})}</annotation>

</semantics>

</math><img src="./72b616ad783a53fea186ae002ece56aaced980c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.326ex; height:2.843ex;" alt="{\displaystyle O({\text{N}})}" loading="lazy"> space is allowed, polynomial time solutions such as <a href="Dijkstra's_algorithm" title="Dijkstra's algorithm">Dijkstra's algorithm</a> have been known and used for decades. But for many years it was unknown if this could be done deterministically in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O({\text{log N}})}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O({\text{log N}})}</annotation>

</semantics>

</math><img src="./d22d4ea0774b991bd277a16090024a17e8eaa605.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.878ex; height:2.843ex;" alt="{\displaystyle O({\text{log N}})}" loading="lazy"> space (class <a href="L_(complexity)" title="L (complexity)">L</a>), though it was known to be possible with randomized algorithms (class RL).

A breakthrough 2004 paper by <a href="Omer_Reingold" title="Omer Reingold">Omer Reingold</a> showed that USTCON is in fact in <a href="L_(complexity)" title="L (complexity)">L</a>,<a href="#cite_note-24">[24]</a> providing an algorithm with asymptotically better space requirement. However, <a href="SL_(complexity)#Omer_Reingold,_2004" title="SL (complexity)">the algorithm's very big constant</a> hidden by the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O({\text{log N}})}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O({\text{log N}})}</annotation>

</semantics>

</math><img src="./d22d4ea0774b991bd277a16090024a17e8eaa605.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.878ex; height:2.843ex;" alt="{\displaystyle O({\text{log N}})}" loading="lazy"> means that on any realistic problem it consumes significantly more memory and computation time than the well known <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O({\text{N}})}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O({\text{N}})}</annotation>

</semantics>

<div class="mw-heading mw-heading3"><h3 id="Low-density_parity-check_codes">Low-density parity-check codes</h3></div>

<a href="Low-density_parity-check_code" title="Low-density parity-check code">Low-density parity-check codes</a>, also known as LDPC or Gallager codes, are an example of an algorithm that was galactic when first developed, but became practical as computation improved. They were originally conceived by <a href="Robert_G._Gallager" title="Robert G. Gallager">Robert G. Gallager</a> in his doctoral dissertation<a href="#cite_note-25">[25]</a> at the <a href="Massachusetts_Institute_of_Technology" title="Massachusetts Institute of Technology">Massachusetts Institute of Technology</a> in 1960.<a href="#cite_note-26">[26]</a><a href="#cite_note-G1962-27">[27]</a> Although their performance was much better than other codes of that time, reaching the <a href="Gilbert%E2%80%93Varshamov_bound_for_linear_codes" title="Gilbert–Varshamov bound for linear codes">Gilbert–Varshamov bound for linear codes</a>, the codes were largely ignored as their iterative decoding algorithm was prohibitively computationally expensive for the hardware available.<a href="#cite_note-28">[28]</a>

Renewed interest in LDPC codes emerged following the invention of the closely related <a href="Turbo_code" title="Turbo code">turbo codes</a> (1993), whose similarly iterative decoding algorithm outperformed other codes used at that time. LDPC codes were subsequently rediscovered in 1996,<a href="#cite_note-MacKay96-29">[29]</a> and became popular as a patent-free alternative.<a href="#cite_note-Closing-30">[30]</a> Even though the turbo code patents have now expired, LDPC codes also have some technical advantages, and are used in many applications today.

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFLiptonRegan2013" class="citation book cs1"><a href="Richard_Lipton" title="Richard Lipton">Lipton, Richard J.</a>; Regan, Kenneth W. (2013). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=eLC9BAAAQBAJ&pg=PA109">"David Johnson: Galactic Algorithms"</a>. People, Problems, and Proofs: Essays from Gödel's Lost Letter: 2010. Heidelberg: Springer Berlin. pp. 109–112. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9783642414220</bdi>.</cite>

</li>

<li id="cite_note-2"><a href="#cite_ref-2">^</a> <cite id="CITEREFFortnow,_L.2009" class="citation journal cs1">Fortnow, L. (2009). <a rel="nofollow" class="external text" href="https://www.cs.cmu.edu/~15326-f23/CACM-Fortnow.pdf">"The status of the P versus NP problem"</a> (PDF). Communications of the ACM. 52 (9): 78–86. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F1562164.1562186">10.1145/1562164.1562186</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:5969255">5969255</a>.</cite>

</li>

<li id="cite_note-3"><a href="#cite_ref-3">^</a> <cite id="CITEREFFortnow2022" class="citation journal cs1">Fortnow, Lance (2022). <a rel="nofollow" class="external text" href="https://dl.acm.org/doi/pdf/10.1145/3460351">"Fifty Years of P Versus NP and the Possibility of the Impossible"</a>. Communications of the ACM. 65 (1): 76–85. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F3460351">10.1145/3460351</a>.</cite>

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> <cite id="CITEREFDavidHoeven2019" class="citation journal cs1 cs1-prop-long-vol">David, Harvey; Hoeven, Joris van der (March 2019). <a rel="nofollow" class="external text" href="https://hal.archives-ouvertes.fr/hal-02070778/document">"Integer multiplication in time O(n log n)"</a>. HAL. hal-02070778.</cite>

</li>

<li id="cite_note-quick-5">^ <a href="#cite_ref-quick_5-0">a</a> <a href="#cite_ref-quick_5-1">b</a> <cite id="CITEREFHarvey2019" class="citation web cs1">Harvey, David (9 April 2019). <a rel="nofollow" class="external text" href="https://theconversation.com/weve-found-a-quicker-way-to-multiply-really-big-numbers-114923">"We've found a quicker way to multiply really big numbers"</a>. The Conversation. Retrieved 9 March 2023.</cite>

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> <cite id="CITEREFLe_Gall2012" class="citation cs2">Le Gall, F. (2012), "Faster algorithms for rectangular matrix multiplication", Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2012), pp. 514–523, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1204.1111">1204.1111</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FFOCS.2012.80">10.1109/FOCS.2012.80</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-7695-4874-6</bdi>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:2410545">2410545</a></cite>

</li>

<li id="cite_note-7"><a href="#cite_ref-7">^</a> <cite id="CITEREFLarry_Hardesty2010" class="citation web cs1">Larry Hardesty (January 19, 2010). <a rel="nofollow" class="external text" href="https://news.mit.edu/2010/explained-shannon-0115">"Explained: The Shannon limit"</a>. MIT News Office.</cite>

</li>

<li id="cite_note-8"><a href="#cite_ref-8">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://ocw.mit.edu/courses/6-451-principles-of-digital-communication-ii-spring-2005/1a3ad00d83d1d042da3328a8edd9edc2_chap13.pdf">"Capacity-approaching codes (Chapter 13 of Principles Of Digital Communication II)"</a> (PDF). <a href="MIT_OpenCourseWare" title="MIT OpenCourseWare">MIT OpenCourseWare</a>. 2005.</cite>

</li>

<li id="cite_note-kkr12-9"><a href="#cite_ref-kkr12_9-0">^</a> <cite id="CITEREFKawarabayashiKobayashiReed2012" class="citation journal cs1">Kawarabayashi, Ken-ichi; Kobayashi, Yusuke; <a href="Bruce_Reed_(mathematician)" title="Bruce Reed (mathematician)">Reed, Bruce</a> (2012). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.jctb.2011.07.004">"The disjoint paths problem in quadratic time"</a>. <a href="Journal_of_Combinatorial_Theory" title="Journal of Combinatorial Theory">Journal of Combinatorial Theory</a>. Series B. 102 (2): 424–435. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.jctb.2011.07.004">10.1016/j.jctb.2011.07.004</a>.</cite>

</li>

<li id="cite_note-10"><a href="#cite_ref-10">^</a> <cite id="CITEREFJohnson,_David_S.1987" class="citation journal cs1">Johnson, David S. (1987). "The NP-completeness column: An ongoing guide (edition 19)". Journal of Algorithms. 8 (2): 285–303. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.114.3864">10.1.1.114.3864</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0196-6774%2887%2990043-5">10.1016/0196-6774(87)90043-5</a>.</cite>

</li>

<li id="cite_note-:0-11"><a href="#cite_ref-:0_11-0">^</a> <cite id="CITEREFBiaoshuai_TaoHongjun_Wu2015" class="citation book cs1">Biaoshuai Tao & Hongjun Wu (2015). Information Security and Privacy. Lecture Notes in Computer Science. Vol. 9144. pp. 39–56. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-319-19962-7_3">10.1007/978-3-319-19962-7_3</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-319-19961-0</bdi>.</cite>

</li>

<li id="cite_note-12"><a href="#cite_ref-12">^</a> <cite id="CITEREFAnna_R._KarlinNathan_KleinShayan_Oveis_Gharan2020" class="citation arxiv cs1">Anna R. Karlin; Nathan Klein; Shayan Oveis Gharan (September 1, 2020). "A (Slightly) Improved Approximation Algorithm for Metric TSP". <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/2007.01409">2007.01409</a> [<a rel="nofollow" class="external text" href="https://arxiv.org/archive/cs.DS">cs.DS</a>].</cite>

</li>

<li id="cite_note-13"><a href="#cite_ref-13">^</a> <cite id="CITEREFKlarreich2020" class="citation web cs1">Klarreich, Erica (8 October 2020). <a rel="nofollow" class="external text" href="https://www.quantamagazine.org/computer-scientists-break-traveling-salesperson-record-20201008/">"Computer Scientists Break Traveling Salesperson Record"</a>. Quanta Magazine.</cite>

</li>

<li id="cite_note-14"><a href="#cite_ref-14">^</a> <cite id="CITEREFHutter2002" class="citation arxiv cs1">Hutter, Marcus (2002-06-14). "The Fastest and Shortest Algorithm for All Well-Defined Problems". <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/cs/0206022">cs/0206022</a>.</cite>

</li>

<li id="cite_note-15"><a href="#cite_ref-15">^</a> <cite id="CITEREFGagliolo2007" class="citation journal cs1">Gagliolo, Matteo (2007-11-20). <a rel="nofollow" class="external text" href="https://doi.org/10.4249%2Fscholarpedia.2575">"Universal search"</a>. Scholarpedia. 2 (11): 2575. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2007SchpJ...2.2575G">2007SchpJ...2.2575G</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.4249%2Fscholarpedia.2575">10.4249/scholarpedia.2575</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1941-6016">1941-6016</a>.</cite>

</li>

<li id="cite_note-16"><a href="#cite_ref-16">^</a> <cite id="CITEREFLiangChengLin2014" class="citation journal cs1">Liang, Faming; Cheng, Yichen; Lin, Guang (2014). "Simulated stochastic approximation annealing for global optimization with a square-root cooling schedule". Journal of the American Statistical Association. 109 (506): 847–863. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1080%2F01621459.2013.872993">10.1080/01621459.2013.872993</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:123410795">123410795</a>.</cite>

</li>

<li id="cite_note-17"><a href="#cite_ref-17">^</a> <cite id="CITEREFIngber,_Lester1993" class="citation journal cs1">Ingber, Lester (1993). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0895-7177%2893%2990204-C">"Simulated annealing: Practice versus theory"</a>. Mathematical and Computer Modelling. 18 (11): 29–57. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.15.1046">10.1.1.15.1046</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0895-7177%2893%2990204-C">10.1016/0895-7177(93)90204-C</a>.</cite>

</li>

<li id="cite_note-18"><a href="#cite_ref-18">^</a> <cite id="CITEREFKargerKleinTarjan1995" class="citation journal cs1">Karger, David R.; Klein, Philip N.; Tarjan, Robert E. (1995-03-01). <a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F201019.201022">"A randomized linear-time algorithm to find minimum spanning trees"</a>. Journal of the ACM. 42 (2): 321–328. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F201019.201022">10.1145/201019.201022</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0004-5411">0004-5411</a>.</cite>

</li>

<li id="cite_note-19"><a href="#cite_ref-19">^</a> <cite id="CITEREFThiesen" class="citation web cs1">Thiesen, Francisco. <a rel="nofollow" class="external text" href="https://github.com/FranciscoThiesen/karger-klein-tarjan">"A C++ implementation for an Expected Linear-Time Minimum Spanning Tree Algorithm(Karger-Klein-Tarjan + Hagerup Minimum Spanning Tree Verification as a sub-routine)"</a>. <a href="GitHub" title="GitHub">GitHub</a>. Retrieved 2022-11-19.</cite>

</li>

<li id="cite_note-20"><a href="#cite_ref-20">^</a> <cite id="CITEREFGeiman_Thiesen" class="citation web cs1">Geiman Thiesen, Francisco. <a rel="nofollow" class="external text" href="https://franciscothiesen.github.io/Linear-Time-MST/">"Expected Linear-Time Minimum Spanning Trees"</a>. franciscothiesen.github.io. Retrieved 2022-11-13.</cite>

</li>

<li id="cite_note-SuccinctDictionaries-21"><a href="#cite_ref-SuccinctDictionaries_21-0">^</a> <cite id="CITEREFLiLiangYuZhou2023" class="citation conference cs1">Li, Tianxiao; Liang, Jingxun; Yu, Huacheng; Zhou, Renfei (6 November 2023). "Tight Cell-Probe Lower Bounds for Dynamic Succinct Dictionaries". 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS). IEEE. pp. 1842–1862. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/2306.02253">2306.02253</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FFOCS57990.2023.00112">10.1109/FOCS57990.2023.00112</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>979-8-3503-1894-4</bdi>.</cite>

</li>

<li id="cite_note-22"><a href="#cite_ref-22">^</a> <cite id="CITEREFBenderFarach-ColtonKuszmaulKuszmaul2021" class="citation arxiv cs1">Bender, Michael; Farach-Colton, Martin; Kuszmaul, John; Kuszmaul, William; Mingmou, Liu (4 Nov 2021). "On the Optimal Time/Space Tradeoff for Hash Tables". <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/2111.00602">2111.00602</a> [<a rel="nofollow" class="external text" href="https://arxiv.org/archive/cs">cs</a>].</cite>

</li>

<li id="cite_note-OptimalBalance-23">^ <a href="#cite_ref-OptimalBalance_23-0">a</a> <a href="#cite_ref-OptimalBalance_23-1">b</a> <cite id="CITEREFNadis2024" class="citation web cs1">Nadis, Steve (8 February 2024). <a rel="nofollow" class="external text" href="https://www.quantamagazine.org/scientists-find-optimal-balance-of-data-storage-and-time-20240208/">"Scientists Find Optimal Balance of Data Storage and Time"</a>. Quanta Magazine. Retrieved 12 February 2025.</cite>

</li>

<li id="cite_note-24"><a href="#cite_ref-24">^</a> <cite id="CITEREFReingold2008" class="citation cs2"><a href="Omer_Reingold" title="Omer Reingold">Reingold, Omer</a> (2008), "Undirected connectivity in log-space", <a href="Journal_of_the_ACM" title="Journal of the ACM">Journal of the ACM</a>, 55 (4): 1–24, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F1391289.1391291">10.1145/1391289.1391291</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=2445014">2445014</a></cite>.

</li>

<li id="cite_note-25"><a href="#cite_ref-25">^</a> <cite id="CITEREFGallager1960" class="citation thesis cs1">Gallager, Robert G. (1960). <a rel="nofollow" class="external text" href="https://dspace.mit.edu/bitstream/handle/1721.1/11804/32786367-MIT.pdf">Low density parity check codes</a> (PDF) (Ph.D thesis). Massachusetts Institute of Technology.</cite>

</li>

<li id="cite_note-26"><a href="#cite_ref-26">^</a> <cite id="CITEREFHardesty2010" class="citation news cs1">Hardesty, L. (January 21, 2010). <a rel="nofollow" class="external text" href="http://web.mit.edu/newsoffice/2010/gallager-codes-0121.html">"Explained: Gallager codes"</a>. MIT News. Retrieved August 7, 2013.</cite>

</li>

<li id="cite_note-G1962-27"><a href="#cite_ref-G1962_27-0">^</a> <cite id="CITEREFGallager1962" class="citation journal cs1">Gallager, R.G. (January 1962). "Low density parity check codes". IRE Trans. Inf. Theory. 8 (1): 21–28. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FTIT.1962.1057683">10.1109/TIT.1962.1057683</a>. <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<a rel="nofollow" class="external text" href="https://hdl.handle.net/1721.1%2F11804%2F32786367-MIT">1721.1/11804/32786367-MIT</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:260490814">260490814</a>.</cite>

</li>

<li id="cite_note-28"><a href="#cite_ref-28">^</a> <cite id="CITEREFAndrewsDivsalarDolinarHamkins2007" class="citation journal cs1">Andrews, Kenneth S; Divsalar, Dariush; Dolinar, Sam; Hamkins, Jon; Jones, Christopher R; Pollara, Fabrizio (2007). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20090620174506/http://coding.jpl.nasa.gov/~hamkins/publications/journals/2007_11_turbo_LDPC.pdf">"The development of turbo and LDPC codes for deep-space applications"</a> (PDF). Proceedings of the IEEE. 95 (11). IEEE: 2142–2156. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FJPROC.2007.905132">10.1109/JPROC.2007.905132</a>. Archived from the original on 2009-06-20. Retrieved 2025-03-04.</cite><code class="cs1-code">{{cite journal}}</code>: CS1 maint: bot: original URL status unknown (link)

</li>

<li id="cite_note-MacKay96-29"><a href="#cite_ref-MacKay96_29-0">^</a> <cite id="CITEREFMacKayNeal1996" class="citation journal cs1"><a href="David_J._C._MacKay" title="David J. C. MacKay">MacKay, David JC</a>; <a href="Radford_M._Neal" title="Radford M. Neal">Neal, Radford M</a> (1996). <a rel="nofollow" class="external text" href="https://docs.switzernet.com/people/emin-gabrielyan/060708-thesis-ref/papers/MacKay96.pdf">"Near Shannon limit performance of low density parity check codes"</a> (PDF). Electronics Letters. 32 (18). IET: 1645–1646. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/1996ElL....32.1645M">1996ElL....32.1645M</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1049%2Fel%3A19961141">10.1049/el:19961141</a>.</cite>

</li>

<li id="cite_note-Closing-30"><a href="#cite_ref-Closing_30-0">^</a> <cite id="CITEREFErico_Guizzo2004" class="citation journal cs1">Erico Guizzo (Mar 1, 2004). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20210902170851/https://spectrum.ieee.org/closing-in-on-the-perfect-code">"CLOSING IN ON THE PERFECT CODE"</a>. IEEE Spectrum. Archived from <a rel="nofollow" class="external text" href="https://spectrum.ieee.org/closing-in-on-the-perfect-code">the original</a> on September 2, 2021.</cite> "Another advantage, perhaps the biggest of all, is that the LDPC patents have expired, so companies can use them without having to pay for intellectual-property rights."

</li>

</ol></div></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-07-29" href="https://en.wikipedia.org/wiki/?title=Galactic_algorithm&oldid=1303159066">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>